1. Field of the Invention
The present invention generally relates to coding of a signal, and more specifically, to an adaptive coding method for estimating probability of entropy encoding.
2. Description of the Related Art
In entropy, arithmetic coding, and decoding, it is known in order to calculate entropy, such that probability estimate of a signal which should be encoded and thereafter should be decoded is required. In arithmetic coding (encoding) and decoding, large data can be compressed by the probability estimate with high precision. As a consequence, the probability estimate is preferably adapted to a change in symbol probability with a priority.
U.S. Pat. No. 5,025,258 discloses such a technique that the adaptive degrees of the symbols to be encoded and decoded to the estimated probability are optimized. This conventional technique will now be described more in detail with reference to FIG. 1 and FIG. 2.
FIG. 1 represents a block diagram for showing the prior art entropy encoder 101 in a simple manner. This entropy encoder 101 accepts the data symbols s(k), and encodes the data symbols S(K) thereof into the data stream a(i). Then, these data symbol S(K) are transferred via a transfer medium 102 to the remotely located entropy decoder 103. To acquire the receiver data stream, the entropy decoder 103 decodes these data symbols S(K) via the transfer medium as a replica of the transferred symbol s(k). The symbol s(k) contains elements (0, - - - , s-1), namely: EQU S(K).epsilon.(0, - - - , s-1) (1)
As explained above, the symbol is given as either a desirable multi-value or a desirable binary value.
As a result, in this example, the encoder 101 includes the arithmetic encoder unit 104, the context extractor 105, the adaptive probability estimator 106, and the line interface 107. Both the symbol s(k) and the probability estimate p(k) are supplied to the arithmetic encoder unit 104 so as to produce the encoded data stream a(i) by executing therein the well known method. Such an arithmetic encoder unit is well known in this technical field. This arithmetic encoder unit is apparently known from, for instance, "Compression of Black-White Image with Arithmetic Coding", IEEE Transaction on Communications VOL. cos-29, pages 858 to 867 issued in June, 1981; "ARITHMETIC ENCODER/DECODER FOR ENCODING/DECODING SYMBOL WITH BINARY ELEMENT" entitled in U.S. Pat. No. 4,633,490 issued on Dec. 30, 1986; and furthermore "Arithmetic Coding for Data Compression", Communications of the ACM, VOL.30, No. 6, pages 520 to 540, issued in June, 1987, which is related to the arithmetic encoder/decoder for encoding/decoding the symbol having the multi-value element. The line interface 107 interfaces the encoded data stream a(i) to transfer this encoded data stream a(i) to the transfer medium 102. This transfer medium 102 sequentially supplies the data stream a(i) to the remotely located decoder 103. As a consequence, the line interface 107 includes such a proper apparatus capable of formatting the data stream into the signal format used in the transfer medium 102. As the well known example of this possible transfer medium 102, there are a T-transfer trunk, an ISDN based subscriber line, and a local area network (LAN). Such a line interface is also well known in this technical field.
The context extractor 105 extracts the context of the received symbol s(k), namely, in this case: EQU C(K).epsilon.(0, - - - , c-1) (2)
In other words, the context extractor 105 produces the context (namely, condition) specific to such a symbol s(k) formed based upon the previously supplied symbol. For example, in an image compression system, the symbol s(k) indicates a color of a present pixel to be encoded, and a context c(k) is determined based on a color of the previous pixel, as explained before. For instance, both a color of a pixel (P) which is located adjacent to the present pixel on the same line and appears immediately before, and a color of a preceding pixel (A) appearing on a line located immediately before the line of the present pixel are employed so as to form a context c(k) for the symbol s(k) adapted to the binary value. In this manner, if both the pixel P and the pixel A are white, then the context c(k) is equal to 0. If both the pixel P and the pixel A are black, then the context c(k) is equal to 1. When the pixel P is black and also the pixel A is white, the context c(k) is equal to 2. When both the pixel P and the pixel A are black, the context c(k) is equal to 3. U.S. Pat. No. 4,633,490 discloses another context extractor (condition producer) with using the binary notation. As apparently from the foregoing descriptions, any ordinarily skilled engineers could extend such a binary-notation context extractor in order to obtain a context to which a multi-value has been applied. The context c(k) which is extracted and expressed is supplied to the adaptive probability estimator 106.
The adaptive probability estimator 106 is employed so as to produce a probability predicted value with respect to an input signal and a relevant context:
The input signal is given as follows: EQU S(K).epsilon.(0, - - - , s-1) (3)
The relevant context is given as follows: EQU C(K).epsilon.(0, - - - , c-1) (4)
The probability predicted value is given as follows: EQU P(K)= (5)
As a consequence, the adaptive probability estimator 106 holds, or saves an array (n.sub.s,c) having dimensions "S" and "C" at a final stage. In this case, the respective elements "n.sub.s,c " of this array are an accumulation of occurrences of the symbol "s", namely "count" in the context "c", and the symbols "s" and "c" are dummy indexes for discriminating a location of "n.sub.s,c " in the array. The adaptive probability estimator 106 may be readily realized by properly programming either a computer or a digital signal processor. However, it is conceivable that this adaptive probability estimator 106 may be formed as a semiconductor chip VLSI circuit in view of the better packaging mode.
A flow chart shown in FIG. 2 represents operations of the adaptive probability estimator 106 in which the adaptive speed of the symbol to be encoded with respect to the estimated probability is optimized to thereby produce the probability predicted value in high precision. The operation of the adaptive probability estimator 106 is commenced from a starting step 201. Next, at an operation block 202, the counts of "n.sub.s,c " are initialized with respect to k=0, and all of values as follows: EQU n.sub.s,c =N.sub.s,c (6) EQU S.epsilon.(0, - - - , s-1) (7) EQU C.epsilon.(0, - - - , c-1) (8)
It should be understood that symbol "N.sub.s,c " is equal to a certain preselected value. At an operation block 203, a next context c(k) is obtained. It should be noted fact that the new context is identical to the previously obtained context. Next, at an operation block 204, a total value of the counts is obtained as 2 for the context c(k) acquired with respect to all of the following values: EQU S.epsilon.(0, - - - , s-1) (9)
In other words, it is obtained as follows: EQU Z= (10)
At an operation block 205, the adaptive probability estimator 106 (FIG. 1) outputs the probability predicted values which are sequentially supplied to the arithmetic encoder unit 104 (FIG. 1). Since this probability predicted value is obtained by the first execution, this probability predicted value is calculated based upon only the initial condition and the acquired context c(k). In the subsequent execution, the probability predicted value is calculated based on a total value of counting the occurrences of the symbol s(k) for the context c(k), namely an accumulated value. At a step 205, the probability predicted value is outputted in this manner. That is to say: EQU Po(k)= (11) EQU Ps-1(k)= (12)
At an operation block 206, a symbol s(k) to be encoded is obtained. At an operation block 207, the count value for the obtained symbol s(k) and the context c(k) is incremented by 1. In other words: EQU ns(k), c(k) (13)
which are incremented by 1. PA1 a first step (502) for entering data to be coded so as to calculate occurrence probability of a symbol with respect to this entered data; PA1 a second step (504) for judging as to whether the symbol with respect to the entered data is equal to a more probable symbol (MPS), or a less probable symbol (LPS); PA1 a third step (505), (509) for calculating a region on a numerical line, which corresponds to the entered data, based upon the judgment result of the second step (504); PA1 a fourth step (508), (510) for calculating an occurrence frequency of either the more probable symbol (MPS) or the less probable symbol (LPS) with respective to the entered input; PA1 a fifth step (511) for comparing an occurrence time accumulated value calculated as the occurrence frequency at the fourth step with a preselected value (threshold value), and for reducing the occurrence time accumulated value by 1/2 in the case that the occurrence time accumulated value reaches the preselected value (threshold value); and PA1 a sixth step (513) for defining the more probable symbol (MPS) and the less probable symbol (LPS) in correspondence with a predetermined region on a numerical line with respect to the data signal to thereby output coordinate values on the numerical line as a corded word. PA1 at the first step, occurrence probability of symbols is obtained by calculating the occurrence time accumulated value (N LPS, N TOTAL). PA1 at the first step, occurrence probability of symbols is obtained by calculating the occurrence time accumulated value (N LPS, N TOTAL). PA1 in such a case that the N MPS value of the more probable symbol (MPS) is larger than, or equal to T2 and also the N LPS value is larger than 1, the occurrence frequency of either the more probable symbol (MPS) or the less probable symbol (LPS) is reduced by 1/2.
At an operation block 208, at least a first characteristic of a set of defined parameters, and at least a second characteristic are obtained. Each element of the set of the defined parameters is an accumulation corresponding to a context of a reception signal to be encoded, namely a function of a count. In other words, a predetermined set of parameters is equal to an occurrence time in which the occurrence of the symbol s(k) with respect to the context c(k) is "accumulated", namely n0,c(k), - - - , ns-1,c(k). In this example, at least the first characteristic corresponds to a minimum value of the accumulated occurrence times with respect to the context c(k). Namely, this minimum value is given as follows: EQU MIN=MINIMUM{n,c(k), . . . ns-1, c(k)} (14)
In this example, at least the second characteristic corresponds to a maximum value of the accumulated occurrence times with regard to the context c(k), namely, this maximum value is given as follows: EQU MAX=MAXIMUM{n,c(k), . . . n-1, c(k)} (15)
At a condition branching point 209, a test is done as to whether at least the first characteristic is equal to, or greater than at least a first threshold value, namely EQU MIN.gtoreq.T1 (16)
Otherwise, a test is made as to whether at least the second characteristic is equal to, or larger than at least a second threshold value, namely EQU MAX.gtoreq.T2 (17)
When at least the first characteristic (MIN) is used, it is important such that the adaptive degree of the adaptive probability estimator 106 (FIG. 1) can be optimized. In this example, the adaptive degree may be optimized by using at least the first characteristic equal to the above-described minimum value MIN, and the smaller threshold value T1 equal to 8. In this manner, in the prior art, the possible signals for the context c(k), namely (0, - - - , s-1) must be produced at least 8 times in order to satisfy the following conditions: EQU MIN.gtoreq.T1 (18)
As a result, the use of at least the first characteristic MIN and at least the first threshold value T1=8 produces such an adaptive speed ideally adapted to the actually evaluated probability value. In order not to interpret that the range in this example is limited, if the application of the binary notation and the probability evaluated as 1/2 are employed as an example, then the accumulated production is adjusted after referring to the context c(k) substantially below-mentioned times: EQU 8+8=16 (19)
With respect to the probability evaluated as 1/4, the accumulated production is adjusted after referring to the context c(k) substantially below-mentioned times: EQU 8+24=32 (20)
With respect to the probability evaluated as 1/8, the accumulated production is adjusted after referring to the context c(k) substantially below-mentioned times: EQU 8+56=64 (21)
In this manner, the adaptive speed becomes fast with respect to the larger (not small) probability value than one as being evaluated whereas the adaptive speed necessarily becomes slow with respect to the smaller probability value than one as being evaluated. The adjustments of the adaptive speed are apparent from a step 209 and a step 210.
At least second characteristic corresponding to the maximum value MAX in this example is employed so as to avoid the overflow occurred in the accumulation of the occurrence of the symbol s(k) contained in the context c(k) in relation to at least the second threshold value T2. If the probability under evaluation is not equal to an excessively small value, then MAX does not constitute such a characteristic which requires the parameter adjustment. As a typical example, the value of the threshold value T2 is 2048. This example implies that another characteristic of a set of parameters is utilized. For instance, a total "Z" obtained at the step 204 is employed instead of MAX.
In this manner, when any one of the below-mentioned condition formula (22) and the following formula (23) can be satisfied, the process operation is returned to the step 209: the condition formula (22) is expressed by: EQU MIN.gtoreq.T1 (22)
Also, the formula (23) is expressed by: EQU MAX.gtoreq.T2 (23)
At an operation block 210, the symbol element accumulated in the context c(k) is adjusted. The adjustment of the adaptive speed is realized at a step 210 in relation to the step 209 which constitutes the cause of the adjustment. For example, the accumulation displayed, namely the count is determined by a so-called "half reduction" set by the following formula (25) about the accumulated occurrence for the context c(k) with respect to all of: EQU S.epsilon.(0, - - - , s-1) (24)
The formula (25) is expressed by: EQU n.sub.s,c (k)=(n.sub.s,c (k)+1)/2 (25)
Conventionally, when the condition of either the formula MIN T.sub.1 or the formula MAX T.sub.2 can be satisfied, the count is adjusted by the same method. As to a certain sort of application, it is convenient to separately adjust each of the above-described conditions. When the count is once adjusted, it should be noted that this adjusted count displays the accumulated occurrence. The adjustment of this accumulated occurrence makes the probability estimate more depend on the newer occurrence in the context c(k). As previously described, the accumulated occurrence produced in accordance with the formula MIN T.sub.1 is adjusted, so that the adaptive degree can be ideally made coincident with the actual probability under evaluation. The adjustment of the accumulated occurrence of the symbol s(k) contained in the context c(k) produced in response to the formula MAX T.sub.2 is to protect the possible arithmetic overflow condition under such a rare case that a very small probability value is estimated.
Thereafter, at a condition branching point 211, a test is made as to whether or not the symbol s(k) corresponds to a final symbol to be encoded/decoded. Normally, the number of symbols to be encoded is known. If this number is conversely not known, then the indication of the number of symbols is supplied to the adaptive probability estimator 106. When the test result is "YES" at the condition branching point 211, the operation of the element of the adaptive probability estimator 106 is accomplished via an END step 212. Conversely, when the test result is "NO" at the condition branching step 211, the control operation is returned to the step 203. Then, the proper operation is repeatedly performed from the step 203 to the step 211 until the test result at the step 211 becomes "YES".
Returning back to the step 209, if the test result becomes "NO", then the control operation is advanced to the step 211 at which the test is made as to whether or not the symbol s(k) corresponds to the final symbol to be encoded (or decoded). If the test result becomes "YES" at the step 211, then the operation of the element of the adaptive probability estimator 106 is accomplished via the END step 212. Conversely, when the test result becomes "NO" at the step 211, an index "k" is produced by being incremented by 1 at a step 213, and the control operation is returned to the step 203. The proper operation is repeatedly performed from the step 203 to the step 211 until the test result becomes "YES" at the step 211.
In the prior art, the decoder 103 includes the line interface 108, the arithmetic decoder unit 109, the context extractor 110, and the adaptive probability estimator 111. The line interface 108 executes the reverse function with respect to the function owned by the line interface 107, so that the input signal is deformatted by the known method so as to acquire the data stream s(i). The arithmetic decoder unit 109 executes the reverse function with regard to the function owned by the arithmetic decoder unit 104. As a consequence, both the received data stream a(i) and the probability estimate derived from the adaptive probability estimator 111 are supplied to the arithmetic decoder unit 109 so as to be used by executing the known method for acquiring the symbol s(k). Such an arithmetic decoder unit is well known in this technical field. This well known coding technique is described in the previous citations, i.e., "Compression of Black-White Image with Arithmetic Coding" IEEE, Transaction on Communications; "Arithmetic Encoder/Decoder for encoding/decoding symbol having binary value" (U.S. Pat. No. 4,633,490); and also "Arithmetic Coding for Data Compression applied to multi-value", Communications of the ACM. Since the structure/operation of the context extractor 110 are identical to those of the context extractor 105, explanations thereof are omitted. Similarly, since the structure/operation of the adaptive probability estimator 104 are identical to those of the adaptive probability estimator 111, explanations thereof are omitted.
In the conventional probability estimating method for the non-storage information source data, since the count value of the counter is reduced by 1/2 without any restriction in order to avoid the overflow of the counter when the count value becomes the maximum value, the estimated probability error is increased. Thus, there is a problem that the coding efficiency is deteriorated.